/*https://leetcode.cn/problems/count-special-integers/description/
2376.统计特殊整数
medium, 方钊堉 2024.10.07
数位DP*/

class Solution {
public:
    // 计算排列数 P(totalOptions, selectionCount) = totalOptions! / (totalOptions-selectionCount)!
    long long calculatePermutations(int totalOptions, int selectionCount) {
        long long result = 1;
        for (int i = 0; i < selectionCount; ++i) {
            result *= (totalOptions - i); // 每次选择减少一个选项
        }
        return result;
    }

    // 计算特殊整数的数量
    int countSpecialNumbers(int number) {
        string numberString = to_string(number); // 将整数转换为字符串以便逐位处理
        int specialNumberCount = 0; // 初始化特殊整数的总数
        int numberLength = numberString.size(); // 获取数字的位数

        // 计算位数少于numberLength的所有特殊整数数量
        for (int currentLength = 1; currentLength < numberLength; ++currentLength) {
            if (currentLength == 1) {
                specialNumberCount += 9; // 1位数: 1-9，共9个可能的特殊整数
            } else {
                // 对于2位及以上的数，第一位可以从1到9选，剩下的位数从剩下的9个数中选
                specialNumberCount += 9 * (int)calculatePermutations(9, currentLength - 1);
            }
        }

        // 统计与number位数相同且<=number的特殊整数数量
        int usedDigitsMask = 0; // 使用位掩码记录已使用的数字
        bool hasUniqueDigits = true; // 标记当前数字是否不包含重复数字
        for (int position = 0; position < numberLength; ++position) {
            int currentDigit = numberString[position] - '0'; // 获取当前位的数字
            int startDigit = (position == 0) ? 1 : 0; // 第一位不能为0，其他位可以从0开始
            for (int candidateDigit = startDigit; candidateDigit < currentDigit; ++candidateDigit) {
                if (usedDigitsMask & (1 << candidateDigit))
                    continue; // 如果候选数字已使用，跳过
                int remainingPositions = numberLength - position - 1; // 剩余需要填充的位置数
                if (remainingPositions > 10 - (position + 1))
                    continue; // 如果剩余位置数超过了可用的唯一数字数，跳过
                // 计算剩余位数的排列数，并累加到特殊整数总数中
                specialNumberCount += calculatePermutations(10 - (position + 1), remainingPositions);
            }
            // 检查当前数字是否已被使用
            if (usedDigitsMask & (1 << currentDigit)) {
                hasUniqueDigits = false; // 发现重复数字，标记为非唯一
                break;
            }
            usedDigitsMask |= (1 << currentDigit); // 标记当前数字为已使用
        }
        if (hasUniqueDigits) {
            specialNumberCount += 1; // 如果number本身是特殊整数，计入总数
        }

        return specialNumberCount; // 返回计算出的特殊整数总数
    }
};